from typing import List


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:

        def _is_valid(x, y):
            return 0 <= x < m and 0 <= y < n and (x, y) not in wall

        def neighbors(x1, y1):
            return [(x2, y2) for (x2, y2) in [(x1 - 1, y1), (x1 + 1, y1), (x1, y1 - 1), (x1, y1 + 1)]
                    if _is_valid(x2, y2)]

        m, n = len(grid), len(grid[0])

        start, end = (-1, -1), (-1, -1)
        wall = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    start = (i, j)
                elif grid[i][j] == 2:
                    end = (i, j)
                elif grid[i][j] == -1:
                    wall.add((i, j))

        aim_num = m * n - len(wall) - 1

        visited = set()

        def dfs(x1, y1):
            # 已经到达终点的情况
            if (x1, y1) == end:
                if len(visited) == aim_num:
                    return 1
                else:
                    return 0

            # 还没到达终点的情况
            ans = 0
            visited.add((x1, y1))
            for (x2, y2) in neighbors(x1, y1):
                if (x2, y2) in visited:
                    continue
                ans += dfs(x2, y2)
            visited.remove((x1, y1))
            return ans

        return dfs(start[0], start[1])


if __name__ == "__main__":
    # 2
    print(Solution().uniquePathsIII([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]]))

    # 4
    print(Solution().uniquePathsIII([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2]]))

    # 0
    print(Solution().uniquePathsIII([[0, 1], [2, 0]]))
